package leetcode.code;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution282 implements IDebug {

	private int target;// 目标值
	private List<String> ans;// 答案
	private char[] nums;// num中间加空格
	private int len;// nums数组长度

	public List<String> addOperators(String num, int target) {
		ans = new ArrayList<>();
		if (num.length() == 1) {
			if (target == Integer.valueOf(num)) {
				ans.add(num);
			}
			return ans;
		}
		this.target = target;// 设置目标
		this.blankNum(num);// num中间塞空格, 填满char[] nums
		f(1);// 决定第i个空格加什么东西
		return ans;
	}

	private void f(int i) {
		if (i == len - 1) {
			checkAnswer();// 判断char[] nums是否是有效的串, 更新答案
			return;
		}
		nums[i] = ' ';// 第i位不放符号
		f(i + 2);
		nums[i] = '-';// 第i位是 -
		f(i + 2);
		nums[i] = '+';// 第i位是 +
		f(i + 2);
		nums[i] = '*';// 第i位是 *
		f(i + 2);
	}

	private void checkAnswer1() {
		char lastop = '+';
		Integer lastNum = null;
		char first = nums[0];
		long cur = nums[0] - '0';
		int len = 1;
		for (int i = 1; i < len; i++) {
			char c = nums[i];
			if (c == ' ')
				continue;
			if (len == 1 && first == '0' && c == '0') {
				return;
			}
			if (c >= '0' && c <= '9') {
				cur = cur * 10 + (nums[i] - '0');
				if (cur > Integer.MAX_VALUE) {
					return;
				}
				len++;
				continue;
			}
			if (c == '+' || c == '-' || c == '*') {
				//if()
			}
		}
	}

	private void checkAnswer() {
		Stack<String> s = new Stack<>();
		StringBuffer cur = new StringBuffer();
		StringBuffer str = new StringBuffer();
		for (int i = 0; i < len; i++) {
			char c = nums[i];
			if (c == ' ')
				continue;
			str.append(c);
			if (c >= '0' && c <= '9') {
				if (cur.length() == 1 && cur.charAt(0) == '0')
					return;// 连着0的数字是错的, 01
				cur.append(c);
				continue;
			}
			if (c == '+' || c == '-' || c == '*') {
				if (!s.isEmpty() && s.peek().equals("*")) {
					s.pop();
					long num = Long.valueOf(s.pop());
					num *= Long.valueOf(cur.toString());
					if (num > Integer.MAX_VALUE) {
						return;// 数值超过int的是错的
					}
					s.add(String.valueOf(num));
				} else {
					long l = Long.valueOf(cur.toString());
					if (l > Integer.MAX_VALUE) {
						return;// 数值超过int的是错的
					}
					s.add(String.valueOf(l));
				}
				s.add(String.valueOf(c));
				cur.setLength(0);
			}
		}
		s.pop();// 结束位'+'
		int ans = 0;
		int last = 0;
		while (!s.isEmpty()) {
			String c = s.pop();
			if (c.equals("+")) {
				ans += last;
			} else if (c.equals("-")) {
				ans -= last;
			} else {
				last = Integer.valueOf(c);
			}
		}
		ans += last;
		if (ans == target) {
			this.ans.add(str.substring(0, str.length() - 1));
		}
	}

	private void blankNum(String num) {
		len = (num.length() << 1);
		nums = new char[len];
		int p = 0;
		for (int i = 0; i < num.length(); i++) {
			nums[p] = num.charAt(i);
			p += 2;
		}
		nums[len - 1] = '+';// 结束位'+'
	}

	public static void main(String[] args) {
		Solution282 so = new Solution282();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();
		so.debug6();
	}

	@Override
	public void debug1() {
		String num = "123";
		int target = 6;
		String str = "[\"1+2+3\", \"1*2*3\"]";
		List<String> e = HelpDebug.str2liststr(str);
		List<String> r = this.addOperators(num, target);
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug2() {
		String num = "232";
		int target = 8;
		String str = "[\"2*3+2\", \"2+3*2\"]";
		List<String> e = HelpDebug.str2liststr(str);
		List<String> r = this.addOperators(num, target);
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug3() {
		String num = "00";
		int target = 0;
		String str = "[\"0+0\", \"0-0\", \"0*0\"]";
		List<String> e = HelpDebug.str2liststr(str);
		List<String> r = this.addOperators(num, target);
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug4() {
		String num = "105";
		int target = 5;
		String str = "[\"1*0+5\",\"10-5\"]";
		List<String> e = HelpDebug.str2liststr(str);
		List<String> r = this.addOperators(num, target);
		HelpDebug.compare(e, r);
	}

	public void debug5() {
		String num = "3456237490";
		int target = 9191;
		String str = "[]";
		List<String> e = HelpDebug.str2liststr(str);
		List<String> r = this.addOperators(num, target);
		HelpDebug.compare(e, r);
	}

	public void debug6() {
		String num = "9999999999";
		int target = 1409865409;
		String str = "[]";
		List<String> e = HelpDebug.str2liststr(str);
		List<String> r = this.addOperators(num, target);
		HelpDebug.compare(e, r);
	}

}
